Network processing devices perform various functions in the processing of data packets, typically by executing a search operation on stored data values. As but two examples, a network processing device can search access control lists (ACLs) or forwarding information bases (FIBs). As is well known, an ACL include a set of rules (data set) that can limit access (e.g., forwarding of packets) to only those packets having fields falling within a particular range. A FIB can include data necessary for forwarding a packet, typically the generation of a “next hop” address in response to a destination address. While ACL searches typically involve a one-step search, in some cases FIB searches can be “algorithmic” requiring more than one search step to arrive at a search result. Thus, a one step ACL search can be considered a flat data set. In contrast, a FIB data set requiring an algorithmic search, can be considered a tree based data set, as a search may be conditional (may branch) depending upon a previous search result.
While types of integrated circuits can be used for executing a search operation on a data set, content addressable memory (CAM) devices enjoy wide application in network processing device due to their rapid searching ability. Conventionally, in many applications, CAM device are employed to search ACLs.
One example of a conventional CAM device is shown in FIG. 14 and designated by the general reference character 1400. A CAM device 1400 can include a number of CAM blocks (1402-0 to 1402-29). Such CAM blocks can be conceptualized as being arranged into block rows, each of which includes block half-rows (1404-0 to 1404-7). Thus, CAM blocks 1402-0 to 1402-3 and 1402-12 to 1402-15 can form a row, with CAM blocks 1402-0 to 1402-3 forming block half-row 1404-0, and CAM blocks 1402-12 to 1402-15 forming block half-row 1404-4.
In the example of FIG. 14, CAM blocks (1402-0 to 1402-29) can be utilized to store ACL data for searching based on search keys. In particular, CAM device 1400 can include control section 1406 that receives an external search key keyET. Control section 1406 can derive any of internal search key keyACL<0> to keyACL<3> from the external search key keyET. Any or all internal search keys keyACL<0> to keyACL<3> can be applied to each block half-row (1404-0 to 1404-7) in a search operation.
While CAM devices can be utilized to search FIBs, in practice for very large databases this is typically not the case. While conventional CAM devices can provide rapid searching capabilities for FIBs, such speed usually comes at a greater device cost, higher power consumption, and lower storage capacity. Because of this, many conventional solutions employ two different devices (e.g., integrated circuits or chips) to support the two different search types (FIB and ACL).
To better understand various aspects and advantages of the disclosed embodiments, two conventional examples for providing search capabilities on multiple data sets will now be described with reference to FIGS. 15A and 15B.
FIG. 15A is a block diagram of a first conventional network processing device. Network processing device 1500 can include a number of ternary CAM (TCAM) devices 1502-0 to 1502-2 formed on a circuit board, or the like. In the particular arrangement shown, a TCAM device 1502-0 can store ACL data sets (tables), while TCAM devices 1502-1 and 1502-2 can store FIB tables. Because TCAM device capacity is typically small relative to the size of FIB tables, multiple TCAM devices (1502-1 1502-2) are used to accommodate desired FIB data.
A drawback to the above conventional approach can be the number of device (e.g., integrated circuits) needed, particularly if two or more TCAM devices are needed to accommodate large FIB tables. A larger number of devices typically results in higher costs and requires more circuit board space. In addition, such a multiple device solution can consume a relatively large amount of power.
FIG. 15B is a block diagram of a second conventional network processing device. Network processing device 1550 can include a ternary CAM (TCAM) device 1552 and a network search engine (NSE) 1554 formed on a circuit board, or the like. A TCAM device 1552 can store ACL data sets (tables). NSE 1554 can be a more specialized device having a larger storage capacity and/or that is more tailored for FIB type search operations. As but one example, an NSE 1554 can be a random access memory (RAM) based device, such as an SRAM based device, that executes FIB searches according to an internal algorithm.
As in the case of the example of FIG. 15A, a drawback to the above conventional approach can be the number of devices (e.g., integrated circuits) needed. While an NSE may reduce the number of chips utilized to form a network processing device, the approach still presents a multiple device solution.
Other conventional arrangements can include a more integrated version of the arrangement shown in FIG. 15B. That is, one or more TCAM devices can be integrated with one or more NSE in either a single integrated circuit, or in a multi-chip module (MCM).
A drawback to all such approaches can be lack of flexibility. In all cases, one device (or instantiation of such a device in single chip case) is dedicated to one type of database (ACL or FIB). This can limit flexibility in how data sets are stored.
In light of the above, it would be desirable to arrive at some way of providing a device capable of searching multiple data sets (e.g., ACLs and FIBs) that does not suffer from the drawback of the conventional cases noted above.